package everydayone.generateParenthesis;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Date 2020/04/09
 * @author 王光浩
 * @Thinking 使用DP
 * @Analysis 时间复杂度O（n^3），空间复杂度O（n） 
 */
public class MyMethodThree {
	public List<String> generateParenthesis(int n) {
		ArrayList<List<String>> ret=new ArrayList<List<String>>(); //保存每一层的可能结果
		List<String> start=new ArrayList<String>();
		ret.add(start);
		for(int i=1;i<=n;i++) {
			List<String> level=new ArrayList<String>();
			for(int j=0;j<i;j++) {
				List<String> now=ret.get(j);
				List<String> next=ret.get(i-j-1);
				if(now.size()==0 && next.size()==0)level.add("()");
				else if(now.size()==0) 
					for(String tem:next)level.add("()"+tem);
				else if(next.size()==0)
					for(String tem:now)level.add("("+tem+")");
				else
					for(int k=0;k<now.size();k++) 
						for(int z=0;z<next.size();z++) 
							level.add("("+now.get(k)+")"+next.get(z));
			}
			ret.add(level);
		}
		return ret.get(n);
	}
}
